/**
 * 458. 可怜的小猪
 * https://leetcode-cn.com/problems/poor-pigs/
 */
public class Solutions_458 {
    public static void main(String[] args) {
        int buckets = 1000, minutesToDie = 15, minutesToTest = 60;  // output: 5
//        int buckets = 4, minutesToDie = 15, minutesToTest = 15;  // output: 2
//        int buckets = 4, minutesToDie = 15, minutesToTest = 30;  // output: 2
//        int buckets = 1, minutesToDie = 1, minutesToTest = 1;  // output: 0

        int result = poorPigs(buckets, minutesToDie, minutesToTest);
        System.out.println(result);
    }

    /**
     * 以 minutesToDie 时长计算，则 minutesToTest 时间内，
     * 一只 pig 可以检验 minutesToTest / minutesToDie + 1桶水
     * 例如：minutesToTest = 60，minutesToDie = 15
     * 则一只 pig 可以检验 60 / 15 + 1 = 5 桶水
     * 编号为 {1, 2, 3, 4, 5} 的 5 只水桶（假设第 5 桶水有毒）
     * 在第 0 分钟时，给 pig 喝第 1 桶水
     * 若第 1 桶水没毒，则 15 分钟后，即第 15 分钟时，给 pig 喝第 2 桶水
     * 若第 2 桶水没毒，则 15 分钟后，即第 30 分钟时，给 pig 喝第 3 桶水
     * 若第 3 桶水没毒，则 15 分钟后，即第 45 分钟时，给 pig 喝第 4 桶水
     * 若第 4 桶水没毒，此时 minutesToTest 时间已过，不能再给 pig 喝水了
     * 我们可以判断出 {1, 2, 3, 4, 5} 水桶中，1,2,3,4 水桶中无毒，有毒的就是最后没喝的
     * 即编号为 5 的水桶内的水有毒
     *
     * 核心：若 1 只 pig 在规定时长内可以检验 5 桶水，则 2 只 pig 可以检验 5 * 5 = 25 桶水，
     * 3 只 pig 可以检验 5 * 5 * 5 = 125 桶水
     * 为什么呢？
     * 以 buckets = 25, minutesToDie = 15, minutesToTest = 60 为例
     * 计算结果是：最少需要两只 pig，才能在规定时间内，检验出 25 桶水中哪桶有毒
     * 1  1  1  1  1    左侧共 25 桶水，其中 2 是有毒的水桶
     * 1  1  2  1  1    让其中一只 pig 在第 1 轮喝第 1 行的水，另一只 pig 在第 1 轮喝第 1 列的水
     * 1  1  1  1  1    n 分钟后，都没有 die，说明有毒的水桶不在第 1 行和第 1 列
     * 1  1  1  1  1    第 2 轮，一只 pig 喝第 2 行的水，一只 pig 喝第 2 列的水
     * 1  1  1  1  1    n 分钟后，喝第 2 行水的 pig 已经 die，说明第 2 行的中有一桶水有毒
     *                  幸存的一只 pig 依次喝第 2 行中未喝过的水（即第 3、第 4、第 5 列）
     *  共 4 轮下来（耗时 minutesToTest），一定可以判断出第 2 行，第 3 列的水桶内有毒
     */
    public static int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        // 一只 pig 在 minutesToTest 时长内，最多可以校验的水桶数量
        int onePig = minutesToTest / minutesToDie + 1;

        int temp = 1;
        // 计算需要 count 只 pig
        int count = 0;
        while (temp < buckets) {
            count ++;
            temp *= onePig;
        }
        return count;
    }
}
